package dp;

import org.junit.Test;

public class SuperEggDrop887 {

    @Test
    public void test() {
        superEggDrop(1, 2);
        superEggDrop(2, 6);
        superEggDrop(3, 14);
        superEggDrop(9, 5000);
    }

    public int superEggDrop(int k, int n) {
        // k表示还有几个鸡蛋可以用来扔, 至少一个
        // n表示剩余几层楼要判定, 与当前所处的楼层无关
        // 为方便计算, 数组比实际长1
        int[][] dp = new int[k+1][n+1];

        // 只有1个鸡蛋, 需要从下往上依次扔
        for (int j = 0; j <= n; j++) {
            dp[1][j] = j;
        }

        // 剩余0层楼要判断, 所以不需要再扔了
        for (int i = 0; i <= k; i++) {
            dp[i][0] = 0;
        }

        // i从2开始, 不要从1开始. i=1 会导致 dp[i-1][p-1] 含义不明确
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                // 这个初值很重要, 对于j层楼, 最多要扔j次
                dp[i][j] = j;
                // 找楼层p来扔
                for (int p = 1; p <= j; p++) {
                    // 在p层扔完后, 求出后续最多需要扔多少次
                    int curMax = Math.max(dp[i][j - p], // 没碎, 继续在高层扔, 高层有(j-p)层, 已经在上一轮j循环中计算出来了.
                                dp[i - 1][p - 1]); // 碎了, 继续在低层扔, 低层有(p-1)层, 已经在上一轮i的循环中计算出来了.
                    // 加1表示在之前的基础上又多扔了一次.
                    dp[i][j] = Math.min(curMax+1, dp[i][j]);
                }
            }
        }
        System.out.format("k: %d, n: %d, count: %d\n", k, n, dp[k][n]);
        return dp[k][n];
    }
}
